package leetCode;

/**
 * 639. 解码方法 II
 * 动态规划
 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：

 'A' -> "1"
 'B' -> "2"
 ...
 'Z' -> "26"
 要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：
 "AAJF" 对应分组 (1 1 10 6)
 "KJF" 对应分组 (11 10 6)
 注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。
 除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。
 给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。
 由于答案数目可能非常大，返回 109 + 7 的 模 。

 示例 1：
 输入：s = "*"
 输出：9
 解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。
 可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。
 因此，"*" 总共有 9 种解码方法。

 示例 2：
 输入：s = "1*"
 输出：18
 解释：这一条编码消息可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条。
 每种消息都可以由 2 种方法解码（例如，"11" 可以解码成 "AA" 或 "K"）。
 因此，"1*" 共有 9 * 2 = 18 种解码方法。

 示例 3：
 输入：s = "2*"
 输出：15
 解释：这一条编码消息可以表示 "21"、"22"、"23"、"24"、"25"、"26"、"27"、"28" 或 "29" 中的任意一条。
 "21"、"22"、"23"、"24"、"25" 和 "26" 由 2 种解码方法，但 "27"、"28" 和 "29" 仅有 1 种解码方法。
 因此，"2*" 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。

 提示：
 1 <= s.length <= 105
 s[i] 是 0 - 9 中的一位数字或字符 '*'
 */
public class NumDecodings {
    static int MOD = 1000000007;

    public static void main(String[] args) {
        numDecodings("1111");
    }

    public static int numDecodings(String s) {
        // dp[i]表示前i个字符的解码方案数
        // 1. 只解码当前一个字符，分成 0、1~9、* 来分别讨论
        // 2. 解码两个字符，分成 **、*X、X*、XX 来分别讨论
        int n = s.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = (decodeOneChar(s.charAt(i - 1)) * dp[i - 1] + (i - 2 < 0 ? 0 : decodeTwoChars(s.charAt(i - 2), s.charAt(i - 1)) * dp[i - 2])) % MOD;
        }

        return (int) dp[n];
    }

    private static int decodeOneChar(char c) {
        if (c == '0') {
            // 0 不能单独解码
            return 0;
        }

        if (c == '*') {
            // * 可选 1~9 任意一个数解码
            return 9;
        }

        // 确定的数字与前一位的解码方案数保持一致
        return 1;
    }

    private static int decodeTwoChars(char c1, char c2) {
        if (c1 == '*' && c2 == '*') {
            // 两个都是 * 号，有 11~19，21~26 共15种选择
            return 15;
        }

        if (c1 == '*') {
            // 如果当前位为 0~6，* 可选1和2
            if (c2 <= '6') {
                return 2;
            }
            // 如果当前位为 7~9，*只能选择1
            return 1;
        }

        if (c2 == '*') {
            // 如果前一位为1，则有 1~9 共9种选择
            if (c1 == '1') {
                return 9;
            }
            // 如果前一位为2，则有 1~6 共6种选择
            if (c1 == '2') {
                return 6;
            }
            // 如果前一位为 0 或 3~9，则不行
            return 0;
        }
        // 两个字符的和是 10 ~ 26 才能够组合在一起，否则不行
        int twoSum = (c1 - '0') * 10 + (c2 - '0');
        if (twoSum >= 10 && twoSum <= 26) {
            return 1;
        }

        return 0;
    }
}
